package william.queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ZhangShenao
 * @date 2024/1/23
 * @description <a href="https://leetcode.cn/problems/implement-stack-using-queues/">...</a>
 */
public class Leetcode225_用队列实现栈 {
    /**
     * 使用两个队列：主队列和备用队列。
     * 当元素压栈时，压入将元素入队到主队列。
     * 当元素弹栈，或查询栈顶元素时：
     * - 将主队列中的元素依次移动到备用队列，直到仅剩一个元素。
     * - 将仅剩的元素出队返回。
     * - 将主队列和备用队列进行交换。
     */
    class MyStack {
        /**
         * 主队列
         */
        private Queue<Integer> main;

        /**
         * 备用队列
         */
        private Queue<Integer> backup;

        /**
         * 构造器
         */
        public MyStack() {
            //初始化主队列和备用队列
            this.main = new LinkedList<>();
            this.backup = new LinkedList<>();
        }

        /**
         * 将元素x压入栈顶
         */
        public void push(int x) {
            //将元素直接入队到主队列
            main.offer(x);
        }

        /**
         * 移除并返回栈顶元素
         */
        public int pop() {
            //首先校验栈是否为空
            if (empty()) {
                throw new UnsupportedOperationException("stack is empty!!");
            }

            //将主队列中的元素依次移动到备用队列,直到仅剩一个元素
            moveUntilOneLeft();

            //将主队列仅剩的元素出队并返回
            int result = main.poll();

            //将主队列与备用队列交换
            swapQueue();

            //返回结果
            return result;

        }

        public int top() {
            //首先校验栈是否为空
            if (empty()) {
                throw new UnsupportedOperationException("stack is empty!!");
            }

            //将主队列中的元素依次移动到备用队列,直到仅剩一个元素
            moveUntilOneLeft();

            //将主队列仅剩的元素出队并返回
            int result = main.poll();

            //将元素重新入队到备用队列
            backup.offer(result);

            //将主队列与备用队列交换
            swapQueue();

            //返回结果
            return result;
        }

        /**
         * 如果栈是空的,返回true；否则返回false
         */
        public boolean empty() {
            //判断两个队列是否同时为空
            return (main.isEmpty() && backup.isEmpty());
        }

        /**
         * 将主队列中的元素依次移动到辅助队列,直到仅剩一个元素
         */
        private void moveUntilOneLeft() {
            if (main.isEmpty()) {
                return;
            }
            int size = main.size();
            for (int i = 0; i < size - 1; i++) {
                backup.offer(main.poll());
            }
        }

        /**
         * 将主队列与备用队列交换
         */
        private void swapQueue() {
            Queue<Integer> tmp = main;
            main = backup;
            backup = tmp;
        }
    }
}
